The invention relates to a method and apparatus for the quantisation of colours in a digital colour image.
The term digital image as used here denotes the digital representation of a document, in which the image information on the document is described by the values of pixels arranged in a raster. These pixel values are frequently collectively referred to as xe2x80x9cdigital image dataxe2x80x9d. The term quantisation also denotes here the reduction of the number of discrete colours present in the digital image data.
Colours can be described within the framework of a colour space, a space defined by axes which characterise specific aspects of colours. One colour space frequently used is, for example, the RGB space, where the axes contain the intensities of the basic colours red, green and blue. Each colour can be represented by co-ordinates in the colour space.
Documents can often contain very many colours. For many applications, such as reproducing a document image on a monitor screen or hard copy, it is desirable to reduce the number of colours, because many imaging processes can reproduce only a limited number of different colours. There are also applications which process a colour image in order to extract therefrom information concerning the contents, such as optical character recognition (OCR) or lay-out analysis. Such applications are frequently obstructed in their operation if a large number of different colours occur in the document image, because a priori they can make no distinction as to the importance of the different colours. A restriction of the number of colours in the image is then all the more desirable.
A known procedure for quantising the colour range of an image into a limited number of colours is to divide the colour space into a number of compartments, whereafter all the colours situated within a compartment are equated to one colour representative of the entire compartment. A number of such procedures are described in Wan, S. J. et al., xe2x80x9cAn Algorithm For Multidimensional Data Clusteringxe2x80x9d, ACM Transactions on Mathematical Software, Vol. 14, No. 2 (June 1988), pp. 153-162. In many of the methods described therein, the variance of the sets of colours for division is used to determine the spread of the dots of the set in the possible division directions.
The known methods, however, are complex and divide the colour space only in a restricted number of directions, namely the directions of the axes of the colour space, so that the division effect is poor. The technique used is not particularly suitable for involving in the division procedure directions other than the directions of the axes of the colour space.
An object of the invention is to solve the said problems of the known methods. To this end, for the purpose of selecting a compartment for division and for the purpose of dividing the selected compartment into new compartments, use is made of the variances of the sets of colours in the compartments in a number of predetermined directions. The variance of the set of colours in a compartment is calculated by determining a covariance matrix which describes this set of colours and calculating therefrom the values of the variance of the set in the relevant directions.
As a result, the division of colour space takes place more effectively and is combined with less computing effort. The covariance matrix is in fact relatively simple to calculate and can be used in simple manner to calculate the variance of the relevant set in an arbitrary direction.
A further improvement of the method according to the invention is achieved by adding procedure steps following the initial division of the colour space, the method further comprising: subjecting resulting sets of colours to a predetermined test; and recombining, on the basis of the results of that test, sets and the compartments corresponding thereto.
The effect of this step is that divisions incorrectly made in the division step, often through other causes, are restored. In this way the final number of colours is further reduced.
Here it should clearly be noted that the method according to the invention does not have as its object to achieve an end result which is as faithful as possible, but rather an image which is very suitable for further interpretation processing.
In another embodiment, the method already described is followed by a post-processing step to remove transition effects along the edges of coloured surfaces in order to prevent their influencing the end result of the quantisation. This post-processing step comprises the application of chain coding.
The invention also relates to the application of the above-described method to a method for the automatic interpretation of a colour image the method comprising: quantising the colours present in the colour image, to a restricted number; making on the basis of the quantisation, a new colour image; interpreting the new colour image. This interpretation step, for example, comprises a classification of image elements into types, such as text elements, photographs and graphic elements, automatic optical character recognition or automatic recognition of securities.
The invention, which includes the quantisation of colours of an image and also the combination of quantisation of colours of an image and interpretation of said image, can be performed in a computer programmed suitably for the purpose and therefore also relates to a computer program and a storage medium on which the computer program is stored.
Advantages of the present invention will become more apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific examples, while indicating preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description.
The present invention will become more fully understood from the detailed description given hereinbelow and the accompanying drawings which are given by way of illustration only, and thus do not limit the present invention.